package com.LeeCode;

/**
 * 找出第 K 个字符 I
 */

public class Code3304 {
    public static void main(String[] args) {
        System.out.println(new Code3304().kthCharacter(500));
    }

    public char kthCharacter(int k) {
        StringBuilder sb = new StringBuilder();
        sb.append('a');
        while (sb.length() < k) {
            int len = sb.length();
            for (int i = 0; i < len; i++) {
                int insert = (sb.charAt(i) - 'a' + 1) % 26;
                sb.append((char) ('a' + insert));
            }
        }
        return sb.charAt(k - 1);
    }

    public char kthCharacter1(int k) {
        int inc = 0;
        for (int i = 31 - Integer.numberOfLeadingZeros(k - 1); i >= 0; i--) {
            if (k > (1L << i)) { // k 在右半边
                inc++;
                k -= 1L << i;
            }
        }
        return (char) ('a' + inc % 26);
    }
}
